package 纯数组;

import java.util.HashSet;
import java.util.Set;

public class No41缺失的第一个正数 {

    /**
     * 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
     * 进阶：你可以实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案吗？
     *
     * 示例 1：
     * 输入：nums = [1,2,0]
     * 输出：3
     * 示例 2：
     * 输入：nums = [3,4,-1,1]
     * 输出：2
     * 示例 3：
     * 输入：nums = [7,8,9,11,12]
     * 输出：1
     *
     * 提示：
     * 0 <= nums.length <= 300
     * -231 <= nums[i] <= 231 - 1
     */

    //非 O(1)空间复杂度,不可
    public int firstMissingPositive(int[] nums) {

        Set<Integer> set=new HashSet<>();
        int min=1;

        for (int i = 0; i < nums.length; i++) {
            if(nums[i]>0){
                set.add(nums[i]);
            }
            while (set.contains(min)){
                min+=1;
            }
        }

        return min;
    }

    //参考解法: O(1)复杂度 原地hash 以正负号为标识
    public int firstMissingPositiveGood(int[] nums) {

        //1.先将负数变为大于nums.length的数,避免对后面的abs()函数干扰
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]<=0){
                nums[i]=nums.length+1;
            }
        }

        //2.现在数组里的数都是正数了,进行正负号打标,标识[1..nums.length-1]范围的数
        for (int i = 0; i < nums.length; i++) {
            int num=Math.abs(nums[i]);
            if(num<=nums.length){
                //注意这里,下标0对应的应该是数字1
                nums[num-1]=-Math.abs(nums[num-1]);//变为负数(避免负负得正)
            }
        }

        //3.根据下标来,找到第一个大于0的数
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]>0){
                return i+1;
            }
        }

        return nums.length+1;
    }

    public static void main(String[] args) {
        No41缺失的第一个正数 n=new No41缺失的第一个正数();
        int[] arr={1,2,0};
        int result = n.firstMissingPositiveGood(arr);
        System.out.println(result);
    }

}
